The present invention relates to maximum likelihood convolution code decoders, and particularly to a trellis connection computer included therein for providing outputs indicative of survivor paths in a maximum likelihood convolution code decoder.
The present invention relates to a trellis connection computer for use in a maximum likelihood convolution code decoder such as one disclosed in U.S. Pat. No. 3,789,360 to Clark and Davis, Jan. 29, 1974, which is assigned to the assignee herein, the disclosure of which is incorporated herein by reference. Also incorporated by reference is U.S. Pat. No. 3,789,359, also issued Jan. 29, 1974 to Clark and Davis and assigned to the assignee herein, which discloses means for synchronizing operation of a convolution code decoder with reception of data. In a convolution code decoder, each received data input is treated as the most recent or last transition or branch into a data state of a current sequence of data states each entered in response to previously received data inputs during previous branch intervals. In decoding convolutional data, a number of possible data sequences are constructed whose respective correlations with the sequence indicated by received data are each computed. An algorithm for selecting the limited number of likely sequences is disclosed by A. G. Viterbi, "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm," IEEE Transactions of Information Theory, Vol. IT-13, No. 2, pp 260-269, April, 1967.
In the use of the Viterbi algorithm, possible data sequences are considered entering each possible data state entered, and the likelihood of entering each state from a prior sequence in response to a current data input is considered. One possible sequence ending in each data state is selected as a survivor sequence. The survivor sequence ending in the data state is the one having the highest correlation with the received data of all of the sequences entering that state. (It is noted that the prior sequences are those which still survived after a similar selection was made at each of the number of preceeding branch intervals in response to previous input data.) In accordance with the algorithm, a comparison is made among survivor sequences to ascertain which sequence is the most highly correlated with the data actually received. The sole survivor sequence thus identified is assumed to be "correct", i.e. to be the sequence that was originally transmitted, and is called the sole survivor sequence. Decoding of message digits based on this assumption is then carried out, for example by the apparatus of the Clark and Davis U.S. Pat. No. 3,789,360 patent.
Decoding apparatus in one form includes tracing apparatus which reconstructs at least one of the survivor sequences step by step by utilizing stored sequential data which describes the branch transitions of paths between states for a sequence under consideration. The tracing apparatus identifies the state or states that were occupied by survivor sequences at the earlier branch interval when the bit currently to be decoded was received. Logic circuits then interpret the state of information to decode a message bit or bits of the original message. A trellis connection computer is the apparatus which provides the data indicative of survivor sequences and sole survivor sequences to the tracing apparatus.
Thus means must be provided to generate the values of the various correlations described above so that survivor and sole survivor sequences may be selected. These values are called metrics. A path metric is a measurement of the goodness of match between a possible sequence and received data. A branch metric measures the likelihood of a transition from a prior data sequence to a particular data state. Path metrics are updated by branch metrics as new data inputs are received. Prior circuits require computation of path metrics. The necessity to calculate metrics may increase operating time over a system in which proper path metrics are conveniently accessed. Further, it is desirable to simplify circuitry providing signals indicative of metric values. This reduces the number of microcircuit "chips" required to fabricate a decoder, thus reducing cost and most likely increasing reliability.
Further, prior convolution code decoders may include complex circuitry due to the circuitry required to accomodate a wide range of large numerical values of metrics. Commonly processing circuitry is binary, and an extra stage of processing circuitry is required for each power of two by which metric values increase. It is desirable to provide a truncated range of metrics while maintaining the ability to select the proper sole survivor sequence.